# -*- coding: utf-8 -*-

'''
@author: 5822 - Duarte Marques & 5955 - João Rosa
@date: 06 de Junho de 2013
@obs: Trabalho de Estruturas de Dados e Algoritmos
      Docente: Prof. Jasnau Caeiro
'''
import sys
import math
from random import uniform
from time import clock
from insertion_sort import insertion_sort
from bubble_sort import bubble_sort
from quicksort import quicksort
from merge_sort import merge_sort
from heapsort import heapsort
from comb_sort import Comb_Sort

class times:
    '''
    Classe em que se medem os tempos e criam os graficos.
    '''
    def __init__(self, numb):
        '''
        Metodo que inicializa a variavem "numb", que vai ser utilizada 
        para saber-mos qual o algoritmo que o utilizador pretende visualizar.
        '''
        self.numb = numb
        
    def times(self):
        '''
        Metodo que executa os tempos, media, variância de cada algoritmo
        e mostra isso representado num grafico "matplotlib".
        '''
        Z = range(50, 1000, 100)
        T = []
        M = 25

        for n in Z:
            A = [uniform(0,100) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = clock()

                if self.numb == 1:
                    quicksort(A).quicksort(A, 0, len(A)-1)
                    pass
                elif self.numb == 2:
                    insertion_sort(A).insertion_sort() 
                    pass
                elif self.numb == 3:
                    bubble_sort(A).bubble_sort()  
                    pass
                elif self.numb == 4:
                    merge_sort(A).merge_sort(0, len(A)-1)
                    pass
                elif self.numb == 5:
                    heapsort(A).heapsort()
                    pass
                elif self.numb == 6:
                    Comb_Sort(A).comb_sort()
                    pass


                t2 = clock()
                tempos.append(t2-t1)

            media = reduce(lambda x, y: x+ y, tempos)/len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos)/len(tempos)
            T.append((n, media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]

        #J = [n/11.95e6 for n, media, var in T]

        import matplotlib.pyplot as plt
        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y, color='b', label='resultado experimental')

        if self.numb == 1 or self.numb == 2 or self.numb == 3 or self.numb == 6:
            if self.numb == 1:
                Z = [n**2/15e6 for n, media, var in T]
                pass
            elif self.numb == 2:
                Z = [n**2/15e7 for n, media, var in T]
                pass
            elif self.numb == 3 or self.numb == 6:
                Z = [n**2/11.95e6 for n, media, var in T]
                pass

            plt.plot(X,Z, color='g', label=u'previsão teórica n*n')
            pass
        elif self.numb == 4 or self.numb == 5:
            W = [n*math.log(n)/15e5 for n, media, var in T]
            plt.plot(X,W, color='r', label=u'previsão teórica n*log(n)')
            pass
        
        #plt.plot(X,J, color='r', label=u'previsão teórica n')
        plt.legend()
        plt.show()

